/*Copyright (c) Microsoft Open Technologies, Inc.  All rights reserved.
Microsoft Open Technologies would like to thank its contributors, a list
of whom are at http://rx.codeplex.com/wikipage?title=Contributors.

Licensed under the Apache License, Version 2.0 (the "License"); you
may not use this file except in compliance with the License. You may
obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied. See the License for the specific language governing permissions
and limitations under the License.*/

// Problem:
//     一个不能少：有k个有序的数组，请找到一个最小的数字范围。使得这k个有序数组中，每个数组都至少有一个数字在该范围中。
//     例如：1: { 4, 10, 15, 24, 26 }；2: { 0, 9, 12, 20 }；3: { 5, 18, 22, 30 }。
//     所得最小范围为[20,24]，其中，20在2中，22在3中，24在1中。
//
//     There are k ordered arrays, to find a smallest/shortest range which meets:
//     there is at least one integer from every array in this range.
//     Example: 1: { 4, 10, 15, 24, 26 }；2: { 0, 9, 12, 20 }；3: { 5, 18, 22, 30 }. 
//     The result range is [20,24], with that, 20 from array #2, 22 from array #3 and 24 from array #1.
//
// Author: everyday (weijie.he@live.com)
//     Run: g++ -g -std=c++0x get_shortest_range.cpp -o short_range.exe && short_range.ex
//


#include <iostream>
#include <queue>
#include <limits>
using namespace std;

// Represent an item within one array
struct data {
    int **arrays;
    int array_index;
    int data_index;

    data() : arrays(nullptr) {
    }

    data(int **pp, int ai, int di) {
        this->arrays = pp;
        this->array_index = ai;
        this->data_index = di;
    }

    data(const data& d) {
        this->arrays = d.arrays;
        this->array_index = d.array_index;
        this->data_index = d.data_index;
    }

    data& operator=(const data& d) {
        if (&d != this) {
            this->arrays = d.arrays;
            this->array_index = d.array_index;
            this->data_index = d.data_index;
        }

        return *this;
    }

    int value() const {
        if (arrays == nullptr) 
            return 0;

        return arrays[array_index][data_index];
    }

    bool operator<(const data &d1) const {
        return this->value() > d1.value();
    }
};

struct range {
    int start;
    int end;

    range() :
        start(numeric_limits<int>::min()), end(numeric_limits<int>::max()) {
    }

    int value() {
        if (end - start < 0)
            return numeric_limits<int>::max();

        return end - start;
    }
};

range get_shortest_range(int **p, int *array_size, int k) {
    // The pq keeps k item in the queue, it makes sure there is one item from every array
    priority_queue<data> pq;
    data max_data;
    range result;

    // Push all first items of arrays into priority queue;
    for (int i=0; i<k; i++) {
        data dd(p, i, 0);
        pq.push(dd);

        if (dd.value() > max_data.value()) {
            max_data = dd;
        }
    }

    while (true) {
        data current = pq.top();
        if (max_data.value() - current.value() < result.value()) {
            result.start = current.value();
            result.end = max_data.value();
        }
        pq.pop();
        // If one of arrays is running out, it's time to say goodbye.
        if (current.data_index >= array_size[current.array_index] - 1)
            break;

        // Push next item for 'current' in its array
        data next(current.arrays, current.array_index, current.data_index + 1);
        pq.push(next);
        if (next.value() > max_data.value())
            max_data = next;
    }

    return result;
}

int main() {
    int **pp = new int*[3];
    *pp = new int[5];
    pp[0][0] = 4;
    pp[0][1] = 10;
    pp[0][2] = 15;
    pp[0][3] = 24;
    pp[0][4] = 26;
    
    *(pp+1) = new int[4];
    pp[1][0] = 0;
    pp[1][1] = 9;
    pp[1][2] = 12;
    pp[1][3] = 20;

    *(pp+2) = new int[4];
    pp[2][0] = 5;
    pp[2][1] = 18;
    pp[2][2] = 22;
    pp[2][3] = 30;

    int array_size[3] = {5, 4, 4};

    range r = get_shortest_range(pp, array_size, 3);

    cout << "range is: [" << r.start << ", " << r.end << "]" << endl;

    return 0;
}
